package com.zql.JianZhiOffer;

import java.util.HashMap;
import java.util.Map;

/**
 * Created By ShuHua on 2022/4/28.
 */
public class Offer_10_II {
    /**
     * 推导
     * 台阶数  跳法 跳法组合
     * 1 1  1
     * 2 2  11，2
     * 3 3  111，12，21
     * 4 5  1111，121，112，22，211
     * 5 8  11111，1211，1121，221，2111，1112，122，212
     * 从上面的推导结果我们可以看出
     * 3个台阶跳法=2个台阶跳法数+1个台阶跳法数
     * 4个台阶跳法=3个台阶跳法数+2个台阶跳法数
     * ....
     *
     * 为什么会这样呢？
     * 在台阶数充足的情况下，我们往后走只有两种跳法，一种是跳一步，一种是跳两步
     * 以跳五个台阶为例，什么情况下我们可以直接跳到第五步呢，一种是从第三个台阶只跳两步，一种是第四个台阶只跳一步，那么跳到五个台阶的跳法就等于跳到第三个台阶的跳法数加上调到第四个台阶的跳法数
     * 当我们走到第三个台阶的时候 假设只跳两步，那么从第三台阶走到第五个台阶的跳法数和跳三个台阶的跳法是一样的 3-5：1112，122，212
     * 当我们在第四个台阶的时候，我们要走到第五个台阶只能跳一步 4-5：11111，1211，1121，221，2111
     * 这个时候我们会发现第三步只跳两个台阶加上第四步只跳一个台阶就是跳5步的跳法数
     *
     * 这个时候得出的结论就是 f(n)=f(n-1)+f(n-2)
     *
     * @param n
     * @return
     */
    static int mod =1000000007;

    /**
     * 这里如果使用递归的话当n>45时计算时间会显著增加
     * @param n
     * @return
     */
    public  static  int numWays(int n) {
        if(n==0)return 1;
        if(n<4) return n%mod;
        return (numWays(n-1)+numWays(n-2))%mod;

    }

    /**
     * 利用map存储前两步的结果
     * 时间复杂度O(n)
     * 空间复杂度O(n)
     * @param n
     * @return
     */
    public  static  int numWays2(int n) {
        Map<Integer,Integer> map = new HashMap<>();
        //这里当n-0时需要返回1 ，因为n的取值范围是【0，100】
        if(n==0)return 1;

        for(int i=1;i<=n;i++){
            if(i<4){
                map.put(i,i%mod);
            } else {
                map.put(i,(map.get(i-1)+map.get(i-2))%mod);
            }
        }
        return map.get(n);

    }

    /**
     * 利用数组
     * 时间复杂度O(n)
     * 空间复杂度O(n)
     * @param n
     * @return
     */
    public  static  int numWays3(int n) {
        int[] res = new int[n+1];
        if(n==0)return 1;
        res[0]=1;
        res[1]=1;

        for(int i=2;i<=n;i++){
            res[i]=(res[i-1]+res[i-2])%mod;
        }
        return res[n];

    }

    /**
     * 优化空间
     * @param n
     * @return
     */
    public  static  int numWays4(int n) {

        if(n==0)return 1;
        int cur=1;
        int next=1;

        for(int i=2;i<=n;i++){
            int tmp = (cur+next)%mod;
            next=cur;
            cur=tmp;

        }
        return cur;

    }

    public static void main(String[] args) {
        System.out.println(numWays4(100));
    }
}
